package org.example.struct.array;

import com.alibaba.fastjson.JSON;

/**
 * @author liyishan
 * @date 2023/7/31 11:02
 * @apiNote
 */

public class Test00167TwoSumPlus {

    public static void main(String[] args) {
        int[] a = new int[]{1, 2, 3, 4, 5, 6};
        int[] res = twoSum(a, 9);
        System.out.println("res:" + JSON.toJSON(res));
    }

    /**
     * 超时
     * @param numbers
     * @param target
     * @return
     */
    public static  int[] twoSum(int[] numbers, int target) {
        for (int i = 0; i < numbers.length; i++) {
            int slow = i + 1;
            int fast = numbers.length - 1;
            while (slow <= fast) {
                int mid = slow + (fast - slow) / 2;
                int sum = numbers[i] + numbers[mid];
                if (sum == target) {
                    return new int[]{i + 1, mid + 1};
                } else if (sum < target) {
                    slow = mid + 1;
                } else {
                    fast = mid;
                }
            }
        }
        return new int[0];
    }

    public static int[] test(int[] numbers, int target) {
        for(int i=0;i<numbers.length; i++) {
            for (int j = i + 1; j < numbers.length; j++) {
                if (numbers[i] + numbers[j] == target) {
                    return  new int[]{i+1 , j+1};
                }
            }
        }
        return new int[0];
    }


    /**
     * 二分查找  不超时
     * @param numbers
     * @param target
     * @return
     */
    public static int[] test1(int[] numbers, int target) {
        for(int i = 0 ;i<numbers.length;i++){
            int low = i+1, high = numbers.length - 1;
            while(low <= high){
                int mid = low + ((high - low) >> 1);
                if(numbers[mid] == target -numbers[i]){
                    return new int[]{i+1,mid+1};
                }else if(numbers[mid] > target -numbers[i]){
                    high = mid -1;
                }else{
                    low = mid +1;
                }
            }
        }
        return new int[]{-1, -1};
    }


    /**
     * 双指针
     * @param numbers
     * @param target
     * @return
     */
    public static int[] test2(int[] numbers, int target) {
        int slow = 0, fast = numbers.length -1;
        while(slow <fast){
            int sum = numbers[slow]+numbers[fast];
            if(sum == target){
                return new int[]{slow+1,fast+1};
            }else if(sum<target){
                slow++;
            }else{
                fast --;
            }
        }
        return new int[]{-1,-1};
    }
}
